package com.kevinkk.monotonicstack;

import java.util.*;

/**
 * nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
 * 给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
 * 对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
 * 返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
 */

/**
 * 本质上是在 nums2 中进行遍历，找到 nums2 中每个元素第一个比其大的元素
 * 但是多了一个要求，只用记录 nums1 中出现过的元素的结果
 */

public class NextGreaterElementI {
    class Solution {
        public int[] nextGreaterElement(int[] nums1, int[] nums2) {
            int[] res = new int[nums1.length];              // 最后的结果只用记录 nums1 中出现的
            Arrays.fill(res, -1);                       // 默认初始值为-1，如果 nums2 中出现了 nums1 中的数字，那么覆盖即可
            Map<Integer, Integer> map = new HashMap<>();    // 便于从 nums1 中的数字获取到其下标
            for (int i = 0; i < nums1.length; i++)
                map.put(nums1[i], i);
            Deque<Integer> st = new ArrayDeque<>();

            // 是在 nums2 中进行遍历
            for (int i = 0; i < nums2.length; i++) {
                // 找到了比之前遍历过的元素大的元素
                while (!st.isEmpty() && nums2[i] > nums2[st.peekFirst()]) {
                    int temp = nums2[st.removeFirst()];     // 之前小的那个元素
                    if (map.containsKey(temp))              // 小的元素如果在 nums1 中出现过
                        res[map.get(temp)] = nums2[i];      // res 中在对应的下标，记录 大的元素
                }
                st.addFirst(i);
            }
            return res;
        }
    }
}
